package leetcode.jianzhioffer;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-11-19 21:08
 **/
public class JianZhiOffer14II {

    public int cuttingRope(int n) {
        //当n <= 3时,返回n - 1;
        if (n <= 3) {
            return n - 1;
        }
        //n == 4时，返回4
        if (n == 4) {
            return 4;
        }
        //n > 4时，尽可能剪出长度为3的段，n <= 4时不在剪段
        //必须使用long类型，否则会越界
        long res = 1;
        int mod = 1000000007;
        while (n > 4) {
            res = res * 3 % mod;
            n -= 3;
        }

        return (int)(n * res % mod);
    }



}
